#include<vector>

//堆排序(需要建堆和维护堆的过程)，时间复杂度O(nlogn),空间复杂度O(1)，有点选择排序的意思，是不稳定的排序

void build(vector<int> &nums,int i,int length){
    int left = i * 2 + 1;
    int right = i * 2 + 2;
    int max = i;
    if(left < length && nums[left] > nums[i])
        max = left;
    if(right < length && nums[right] > nums[i])
        max = right;
    if(max != i){
        int temp = nums[max];
        nums[max] = nums[i];
        nums[i] = temp;
        build(nums,max,length);
    }
}

void heap_sort(vector<int> &nums,int length){
    for(int i = length/2-1;i >= 0;i--){
        build(nums,i,length);
    }
    for(int i = length - 1;i >= 0;i--){
        int temp = nums[0];
        nums[0] = nums[i];
        nums[i] = temp;
        build(nums,0,i);
    }
}